package stu.day48;

public class hw3 {

    public int findCircleNum(int[][] isConnected) {

        // 城市的数量
        int n = isConnected.length;

        // 初始化并查集
        UnionFind uf = new UnionFind(n);

        // 遍历每个顶点，将当前顶点与其邻接点进行合并
        for (int i = 0; i < n; i++) {
            // 由于这个二维数组是镜像对称的
            // 所以 j 可以从 i + 1 开始
            for (int j = i + 1; j < n; j++) {
                // 如果第 i 个城市和第 j 个城市直接相连
                if (isConnected[i][j] == 1) {
                    // 连通起来
                    uf.union(i, j);
                }
            }
        }
        // 返回最终合并后的集合的数量
        return uf.count;
    }
}

// 并查集
class UnionFind {

    // 使用一维数组用来记录每个城市的父城市
    // 如果自己就是根城市，那么 roots[i] = i，即自己指向自己
    // 如果自己不是根城市，则 roots[i] = roots id
    int[] roots;

    // 省份数量
    int count;

    public UnionFind(int n) {
        // 使用一维数组用来记录每个城市的父城市
        roots = new int[n];
        for (int i = 0; i < n  ; i++) {
            // 默认每个城市的父城市是自己本身
            roots[i] = i;
        }
        // 所以一开始有 n 个省份
        count = n ;
    }

    // 寻找 i 的父城市
    public int find(int i) {

        // 如果发现当前城市的父城市是自己本身
        if (i == roots[i]) {
            // 返回自己就行
            return i;
        }

        // 否则不断的去向上寻找
        // 这里采取了路径压缩的方法
        // roots[i] 记录的是 i 这个城市的父城市
        // find(roots[i]) 表示去寻找 roots[i] 的父城市
        // 遍历父城市的同时，把父城市的父城市也改成根城市
        roots[i] = find(roots[i]);

        // 返回结果
        return roots[i];
    }

    // 连通操作
    public void union(int p, int q) {
        // 寻找 p 的父城市
        int pRoot = find(p);

        // 寻找 q 的父城市
        int qRoot = find(q);

        // 如果两者的父城市不同
        // 那么需要采取操作把 p 和 q 所在的两堆城市合到一起
        if (pRoot != qRoot) {
            // 也就是把其中一个的最上面的城市挂过来就行
            roots[pRoot] = qRoot;
            // 与此同时，两堆城市变成了一堆城市
            count--;
        }
    }
}
